package everyday.m20230309;

public class Q20230325 {

    public int findLengthOfShortestSubarray(int[] arr) {
        // 寻找需要删除的子数组，假设该子数组为arr[i]...arr[j]
        // 则应该满足arr[i] < arr[i-1]，arr[j] < arr[i-1]，以及arr[j+1]>=arr[i-1]
        int n = arr.length;
        int j = arr.length - 1;
        // 先从后往前找，找到第一个不符合的元素
        while (j > 0 && arr[j - 1] <= arr[j]) {
            j --;
        }
        if (j == 0) {
            return 0;
        }
        // 找到了，那么arr[j,n]肯定符合标准
        int res = j;
        // 更新更加符合标准的
        for (int i = 0; i < n; i++) {
            while (j < n && arr[j] < arr[i]) {
                j++;
            }
            res = Math.min(res, j - i - 1);
            if (i + 1 < n && arr[i] > arr[i + 1]) {
                break;
            }
        }
        return res;
    }
}
